#!/bin/sh
# gen-xarray
# vim: ft=sh ts=4 sw=4 et
# Ralph Becket <rafe@csse.unimelb.edu.au>
# Thu Apr  1 19:44:15 EST 2010
#
# usage: gen-xarray --help
# or     gen-xarray <type name> <item type> [option ...] [<.h file> ...]
# where option is one of
#   --init-size <n>
#   --malloc <malloc func>
#   --free <free func>
#
# Generates <type name>.h and <type name>.c files for an
# expanding array of <item type> values.

PROGNAME=`basename $0`

ARGS=$@

usage () {
    cat << END_OF_USAGE
usage: $PROGNAME --help
or     $PROGNAME <type name> <item type> [option ...] [<.h file> ...]
where option is one of
  --init-size <n>
  --malloc <malloc func>
  --free <free func>
Generates <type name>.h and <type name>.c files for an
expanding array of <item type> values.
END_OF_USAGE
}

if test "$1" = "--help"
then
    usage
    exit 0
fi

if test "$#" -lt 2
then
    usage
    exit 1
fi

case "$1" in
-*)
    usage
    exit 1
    ;;
esac
TYPE_NAME=$1
shift

case "$1" in
-*)
    usage
    exit 1
    ;;
esac
ITEM_TYPE=$1
shift

INIT_SIZE=8
MALLOC=malloc
FREE=free
while test "$#" -gt 0
do
    case "$1" in
    --init-size)
        INIT_SIZE=$2
        shift 2
        ;;
    --malloc)
        MALLOC=$2
        shift 2
        ;;
    --free)
        FREE=$2
        shift 2
        ;;
    *)
        INCLUDES=$INCLUDES"#include \"$1\""
        shift
        ;;
    esac
done
INCLUDES=`echo $INCLUDES | sed 's/#/\n#/g'`

cat > ${TYPE_NAME}.h << END_OF_H
/*
** ${TYPE_NAME}.h
** Automatically generated with
** $PROGNAME $ARGS
*/ 

#ifndef __${TYPE_NAME}_h__
#define __${TYPE_NAME}_h__
${INCLUDES}

struct ${TYPE_NAME} {
        /* Items item[0]..item[size-1] are valid. */
    int size;
        /* The maximum size of the array before resizing is needed. */
    int max_size;
        /* The item array is allocated to have max_size cells. */
    ${ITEM_TYPE} item[1];
};
typedef struct ${TYPE_NAME} ${TYPE_NAME};

    /*
    ** Initialise a new, empty, xarray.
    */
${TYPE_NAME} *
${TYPE_NAME}_init();

    /*
    ** Add an item to the end of an xarray (may resize the array).
    */
${TYPE_NAME} *
${TYPE_NAME}_push(${TYPE_NAME} *a, ${ITEM_TYPE} x);

    /*
    ** Remove the last item from the xarray (aborts with an error
    ** if the xarray is empty.
    */
${ITEM_TYPE}
${TYPE_NAME}_pop(${TYPE_NAME} *a);

    /*
    ** Swap two elements of an xarray (the unsafe version does not
    ** check the indices for validity, the other version aborts with
    ** an error if the indices are out of range).
    */
void
${TYPE_NAME}_unsafe_swap(${TYPE_NAME} *a, int i, int j);
void
${TYPE_NAME}_swap(${TYPE_NAME} *a, int i, int j);

    /*
    ** Concatenate the second xarray on to the first.
    */
${TYPE_NAME} *
${TYPE_NAME}_append(${TYPE_NAME} *a, ${TYPE_NAME} *b);

#endif /* ${TYPE_NAME}_h */

END_OF_H

cat > ${TYPE_NAME}.c << END_OF_C
/*
** ${TYPE_NAME}.h
** Automatically generated with
** $PROGNAME $ARGS
*/ 

#include <stdlib.h>
#include <stdio.h>
#include "${TYPE_NAME}.h"

${TYPE_NAME} *
${TYPE_NAME}_init()
{
    ${TYPE_NAME} *a =
        (${TYPE_NAME} *)${MALLOC}(
            sizeof(${TYPE_NAME}) +
            (${INIT_SIZE} - 1) * sizeof(${ITEM_TYPE})
        );
    if (a == NULL) {
        fprintf(stderr, "${TYPE_NAME}_init: call to ${MALLOC} returned NULL.\n");
        exit(1);
    }
    a->size = 0;
    a->max_size = ${INIT_SIZE};
    return a;
}

${TYPE_NAME} *
${TYPE_NAME}_push(${TYPE_NAME} *a, ${ITEM_TYPE} x)
{
    unsigned int size = a->size;
    unsigned int max_size = a->max_size;

    if (size == max_size) {
        int i;
        int new_max_size = max_size + max_size;
        ${TYPE_NAME} *old_a = a;
        ${TYPE_NAME} *new_a =
            (${TYPE_NAME} *)${MALLOC}(
                sizeof(${TYPE_NAME}) +
                (new_max_size - 1) * sizeof(${ITEM_TYPE})
            );

        if (new_a == NULL) {
            fprintf(stderr, "${TYPE_NAME}_push: call to ${MALLOC} returned NULL.\n");
            exit(1);
        }

        new_a->size = size;
        new_a->max_size = new_max_size;

        for (i = 0; i < size; i++) {
            new_a->item[i] = old_a->item[i];
        }

        ${FREE}(old_a);

        a = new_a;
    }

    a->item[size] = x;
    a->size++;

    return a;
}

${ITEM_TYPE}
${TYPE_NAME}_pop(${TYPE_NAME} *a)
{
    if (a->size == 0) {
        fprintf(stderr, "${TYPE_NAME}_pop: empty ${TYPE_NAME}.\n");
        exit(1);
    }

    a->size--;

    return a->item[a->size];
}

void
${TYPE_NAME}_unsafe_swap(${TYPE_NAME} *a, int i, int j)
{
    ${ITEM_TYPE} tmp = a->item[i];
    a->item[i] = a->item[j];
    a->item[j] = tmp;
}

void
${TYPE_NAME}_swap(${TYPE_NAME} *a, int i, int j)
{
    int size = a->size;

    if (0 <= i && i < size && 0 <= j && j < size) {
        ${TYPE_NAME}_unsafe_swap(a, i, j);
    } else {
        fprintf(stderr, "${TYPE_NAME}_swap: index out of range.\n");
        exit(1);
    }
}

${TYPE_NAME} *
${TYPE_NAME}_append(${TYPE_NAME} *a, ${TYPE_NAME} *b)
{
    /*
    ** This is asymptotically efficient :-)
    */
    int i;

    for (i = 0; i < b->size; i++) {
        a = ${TYPE_NAME}_push(a, b->item[i]);
    }

    return a;
}

END_OF_C
